{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 31.1 Elementary number-theoretic notions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 31.1-1\n",
    "\n",
    "> Prove that if $a > b > 0$ and $c = a + b$, then $c ~\\text{mod}~ a = b$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{array}{rll}\n",
    "c ~\\text{mod}~ a &=& (a + b) ~\\text{mod}~ a \\\\\n",
    "&=& (a ~\\text{mod}~ a) + (b ~\\text{mod}~ a) \\\\\n",
    "&=& 0 + b \\\\\n",
    "&=& b\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 31.1-2\n",
    "\n",
    "> Prove that there are infinitely many primes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{array}{rl}\n",
    "& ((p_1 p_2 \\cdots p_k) + 1) ~\\text{mod}~ p_i \\\\\n",
    "=& (p_1 p_2 \\cdots p_k) ~\\text{mod}~ p_i + (1 ~\\text{mod}~ p_i) \\\\\n",
    "=& 0 + 1 \\\\\n",
    "=& 1\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 31.1-3\n",
    "\n",
    "> Prove that if $a ~|~ b$ and $b ~|~ c$, then $a ~|~ c$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* If $a ~|~ b$, then $b = a \\cdot k_1$.\n",
    "* If $b ~|~ c$, then $c = b \\cdot k_2 = a \\cdot (k_1 \\cdot k_2) = a \\cdot k_3$, then $a | c$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 31.1-4\n",
    "\n",
    "> Prove that if $p$ is prime and $0 < k < p$, then $\\text{gcd}(k, p) = 1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* If $k \\ne 1$, then $k~\\nmid~p$.\n",
    "* If $k = 1$, then the divisor is $1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 31.1-5\n",
    "\n",
    "> Prove Corollary 31.5.\n",
    "\n",
    "> For all positive integers $n$, $a$, and $b$, if $n~|~ab$ and $\\text{gcd}(a, n) = 1$, then $n~|~b$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If $n ~|~ ab$, then $ab = kn$, then $b = nk / a$; since $\\text{gcd}(a, n) = 1$, then $n / a$ could not be an integer; since $b$ is an integer, then $k / a$ must be an integer, $b = nk / a = n (k / a) = n k'$, then $n ~|~ b$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 31.1-6\n",
    "\n",
    "> Prove that if $p$ is prime and $0 < k < p$, then $p ~|~ \\binom{p}{k}$. Conclude that for all integers $a$ and $b$ and all primes $p$,\n",
    "\n",
    "> $(a + b)^p \\equiv a^p + b^p ~(\\text{mod}~p)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{array}{rlll}\n",
    "(a + b) ^ p &\\equiv& \\displaystyle a^p + \\binom{p}{1} a^{p-1}b^{1} + \\cdots + \\binom{p}{p-1} a^{1}b^{p-1} + b^p &(\\text{mod}~ p) \\\\\n",
    "&\\equiv& a^p + 0 + \\cdots + 0 + b^p &(\\text{mod}~ p) \\\\\n",
    "&\\equiv& a^p + b^p &(\\text{mod} p)~ \\\\\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 31.1-7\n",
    "\n",
    "> Prove that if $a$ and $b$ are any positive integers such that $a~|~b$, then\n",
    "\n",
    "> $(x~\\text{mod}~b)~\\text{mod}~a = x~\\text{mod}~a$\n",
    "\n",
    "> for any $x$. Prove, under the same assumptions, that\n",
    "\n",
    "> $x \\equiv y ~(\\text{mod}~ b)$ implies $x \\equiv y ~(\\text{mod}~a)$\n",
    "\n",
    "> for any integers $x$ and $y$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose $x = kb + c$, then $(x~\\text{mod}~b)~\\text{mod}~a = c~\\text{mod}~a$, and $x~\\text{mod}~a = (kb + c)~\\text{mod}~a = (kb~\\text{mod}~a) + (c~\\text{mod}~a) = c~\\text{mod}~a$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 31.1-8\n",
    "\n",
    "> For any integer $k > 0$, an integer $n$ is a __*$k$th power*__ if there exists an integer $a$ such that $a^k = n$. Furthermore, $n > 1$ is a __*nontrivial power*__ if it is a $k$th power for some integer $k > 1$. Show how to determine whether a given $\\beta$-bit integer $n$ is a nontrivial power in time polynomial in $\\beta$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Iterate $a$ from $2$ to $\\sqrt{n}$, and do binary searching."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 31.1-9\n",
    "\n",
    "> Prove equations (31.6)-(31.10)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\dots$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 31.1-10\n",
    "\n",
    "> Show that the gcd operator is associative. That is, prove that for all integers $a$, $b$, and $c$,\n",
    "\n",
    "> $\\text{gcd}(a, \\text{gcd}(b, c)) = \\text{gcd}(\\text{gcd}(a, b), c)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\dots$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 31.1-11 $\\star$\n",
    "\n",
    "> Prove Theorem 31.8."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 31.1-12\n",
    "\n",
    "> Give efficient algorithms for the operations of dividing a $\\beta$-bit integer by a shorter integer and of taking the remainder of a $\\beta$-bit integer when divided by a shorter integer. Your algorithms should run in time $\\Theta(\\beta^2)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Shift left until the two numbers have the same length, then repeatedly subtract with proper multiplier and shift right."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 31.1-13\n",
    "\n",
    "> Give an efficient algorithm to convert a given $\\beta$-bit (binary) integer to a decimal representation. Argue that if multiplication or division of integers whose length is at most $\\beta$ takes time $M(\\beta)$, then we can convert binary to decimal in time $\\Theta(M(\\beta) \\lg \\beta)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bin2dec(s):\n",
    "    n = len(s)\n",
    "    if n == 1:\n",
    "        return ord(s) - ord('0')\n",
    "    m = n // 2\n",
    "    h = bin2dec(s[:m])\n",
    "    l = bin2dec(s[m:])\n",
    "    return (h << (n - m)) + l"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
